perm filename A25.TEX[106,RWF] blob
sn#826047 filedate 1986-10-08 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \magnification\magstephalf
C00022 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
January\or February\or March\or April\or May\or June\or
July\or August\or September\or October\or November\or December\fi
\space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a25.tex[106,phy] \today\hfill}
\bigskip
\line{\bf Symbolic Execution\hfill}
\bigskip
We want to compute an approximate value of $e↑x$ by summing the series
$$e↑x=1+x+{x↑2\over 2!}+{x↑3\over 3!}+\cdots\;.$$
If we keep the successive terms ($1,x,x↑2/2$, etc.) in variable~{\tt T},
the partial sums ($1,1+x$, etc.) in variable~{\tt S}, and a counter
in~{\tt C}, the main iteration looks like
\smallskip
{\obeylines\obeyspaces\let =\ \tt
WHILE ? DO
BEGIN
C:=C+1;
T:=T*X/C
S:=S+T
END
}
\smallskip
\noindent
After the first iteration, we want to have
$${\tt C} =1,\quad {\tt T} =x,\quad\hbox{and}\quad {\tt S} =1+x\,.$$
How should {\tt C}, {\tt T}, and {\tt S} be initialized? For this we need the idea
of {\sl symbolic execution\/}. We let $C↓0$, $T↓0$, and $S↓0$ stand for
the original values of {\tt C}, {\tt S}, and~{\tt T}, and execute the body of the
iteration symbolically on formulas containing $C↓0$, $T↓0$, and~$S↓0$.
$$\vcenter{\halign{\lft{#}\qquad&$\ctr{#}$\qquad&$\ctr{#}$\qquad%
&$\ctr{#}$\cr
&{\tt C}&{\tt T}&{\tt S}\cr
\multispan4\hrulefill\cr
\noalign{\smallskip}
Initially&C↓0&T↓0&S↓0\cr
\noalign{\medskip}
After {\tt C:=C+1}:&C↓0+1&T↓0&S↓0\cr
\noalign{\medskip}
After {\tt T:=T*X/C}:&C↓0+1&\displaystyle{T↓0x\over C↓0+1}&S↓0\cr
\noalign{\medskip}
After {\tt S:=S+T}:&C↓0+1&\displaystyle{T↓0x\over C↓0+1}%
&\displaystyle{S↓0+{T↓0x\over C↓0+1}}\cr}}$$
\noindent
Equating these final values with what we want them to be,
$$C↓0+1=1\,,\quad {T↓0x\over C↓0+1}=x\quad
S↓0+{T↓0x\over C↓0+1}=1+x\,,$$
and solving gives $C↓0=0$, $T↓0=1$, $S↓0=1$. The initialization should
therefore be
$$C:=0\,;\quad T:=1.0\,;\quad S:=1.0\,;$$
Symbolic execution is a reliable way to initialize a complicated iteration
correctly.
\vfill\eject
{\rmn
{\narrower\smallskip\noindent
\noindent{\bf Exercise:} (Symbolic Execution)
\noindent
The program fragment below is the main iteration of a program to compute
the numerator and denominator of the continued fraction
$$\vcenter{\offinterlineskip
\halign{$#$&$#$&$#$&$#$&$#$&$#$&$#$\cr
\quad 1\quad\cr
\noalign{\smallskip}
\multispan7\hrulefill\cr
\noalign{\smallskip}
\quad 2\quad &+\quad&\quad 3\quad\cr
\noalign{\smallskip}
&&\multispan5\hrulefill\cr
\noalign{\smallskip}
&&\quad 4\quad&+\quad&\quad 5\quad\cr
\noalign{\smallskip}
&&&&\multispan3\hrulefill\cr
\noalign{\smallskip}
&&&&\quad 6\quad&+\quad&\quad 7\quad\cr
\noalign{\smallskip}
&&&&&&\multispan1\hrulefill\cr
\noalign{\smallskip}
&&&&&&\quad 8\quad\cr}}$$
using the simplification rule
$${A\over B+{\hbox{NUM}\over\hbox{DEN}}}={A*\hbox{DEN}\over
B*\hbox{DEN}+\hbox{NUM}}\,.$$
\medskip
{\obeylines\obeyspaces\let =\ \tt
FOR I:=4 DOWNTO 1 DO
BEGIN
B:=2*I; A:=B-1;
TEMP:=A*DEN;
DEN:=B*DEN+NUM;
NUM:=TEMP
END
}
\smallskip\noindent
Use symbolic execution to initialize it, so that after the first
iteration
$${\tt NUM} =7\qquad\hbox{and}\qquad{\tt DEN} =8.$$
\bigskip
\noindent{\bf Solution.}
Initially, let
$${\tt I}=4\,,\quad {\tt NUM}=N\,,\quad {\tt DEN}=D\,,\quad {\tt TEMP}=T\,.$$
We then get, successively:
$$\eqalign{&{\tt B} =2I=8\cr
&{\tt A} = {\tt B}-1=7\cr
&{\tt TEMP} = {\tt A} * {\tt DEN}=7D\cr
&{\tt DEN} = {\tt B} * {\tt DEN} + {\tt NUM}=8D+N\cr
&{\tt NUM} = {\tt TEMP} =7D\cr}$$
Equating $7D=7$, $8D+N=8$, we must have $D=1$, $N=0$, so the correct
initialization is
$$\hbox{{\tt NUM:=0;\quad DEN:=1;}}$$
\smallskip}
}
\vfill\eject
\line{\bf (Invariants, Symbolic Execution)\hfill}
\bigskip
I can change an $n\times n$ square into an $(n+1)\times (n+1)$ square by
attaching a $1\times n$ strip to the side, then a $1\times (n+1)$ strip
to the bottom:
\figbox 1.7truein:
\noindent
That suggests the folowing cute program, with the important
invariants as comments,
to print the perfect squares without multiplication:
{\obeylines\obeyspaces\let =\ \tt
S:=0;
FOR I:=0 TO 10 DO
BEGIN
(* S=I(I-1) *)
S:=S+I; (* S=I*I *)
WRITELN(I,S);
S:=S+I (* S=I(I+1) *)
END
}
\smallskip
This program, an elaboration of the same idea,
prints a table of integers with their squares and cubes,
without doing any multiplication:
{\obeylines\obeyspaces\let =\ \tt
S:=0; C:=0;
FOR I:=0 TO 10 DO
BEGIN
(* S=(I-1)*I, C=(I-1)*I*I *)
S:=S+I; (* =I*I *)
C:=C+S; (* =I*I*I *)
WRITELN(I,S,C); (* NUMBER, SQUARE, CUBE *)
C:=C+S; (* =I*I*(I+1) *)
S:=S+I; (* =I*(I+1) *)
C:=C+S; (* =I*(I+1)+(I+1) *)
(* READY FOR I+1 *)
}
\vfill\eject
\line{\bf Base Ten Logarithms (Symbolic Execution).\hfil}
\smallskip
\line{\it ``Throw Another Log upon the Fire.''\hfil}
\smallskip
If I have a ``four-function'' calculator, capable of adding, subtracting,
multiplying, and dividing, and I~want to find the base~ten logarithm
of a given number~$X$ accurately, what algorithm could I~use? Suppose the
number is~3. I~can raise it to a large power by multiplication:
$$3↑{10}=59049=10↑4\times 5.9049\,.$$
Symbolically taking logs of both sides,
$$\eqalign{10\log 3&=4+\log 5.9049\cr
\log 3&=0.4+0.1\log 5.9049\,;\cr}$$
since $0<\log 5.9049<1$, this shows that $\log 3=0.4\ldots$, so I~have
the first digit of the logarithm. To get the next digit the same way,
though, would entail calculating $3↑{100}=59049↑{10}$, which is a
48~digit number, too large for my calculator.
Instead, I can write 59049 in scientific notation, $5.9049\times 10↑4$,
and raise it to the tenth power half numerically, half symbolically:
$$\eqalign{3↑{100}&=59049↑{10}=(5.9049\times 10↑4)↑{10}=5.9049↑{10}\times 10↑{40}\cr
&=51537752\times 10↑{40}=5.1537752\times 10↑{47}\,;\cr
\noalign{\smallskip}
\log 3&=0.47+0.01\log 5.1537752=0.47\ldots\,,\cr}$$
and I have the second digit. Continuing,
$$\eqalign{3↑{1000}&=(5.1537752\times 10↑{47})↑{10}\cr
&=5.1537752↑{10}\times 10↑{470}\cr
&=13220708\times 10↑{470}\cr
&=1.3220708\times 10↑{477}\,;\cr
\noalign{\smallskip}
\log 3&=0.477\ldots\,,\cr}$$
and the way to continue the calculation is obvious. A snapshot table
[defined?] of the complete computation to eight decimal places is:
$$\vcenter{\halign{$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$\qquad
&$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$\cr
X&A&B&C&D&E\cr
\noalign{\smallskip}
\noalign{\hrule}
\noalign{\smallskip}
3&?&?&?&3&?\cr
&59049&4&4&5.9049&10\cr
&51537752&7&47&5.1537752&100\cr
&13220708&7&477&1.320708&1000\cr
&16.313502&1&4771&1.6313502&10↑4\cr
&133.49713&2&47712&1.3349713&10↑5\cr
&17.97709&1&477121&1.797709&10↑6\cr
&352.52826&2&4771212&3.5252826&10↑7\cr
&296441.78&5&47712125&2.9644178&10↑8\cr}}$$
so $\log 3=0.47712125$.
The general pattern is
$$\eqalign{A&:=D↑{10}\,;\cr
B&:=(\hbox{number of integer digits of }A)-1\,;\cr
C&:=10*C+B\,;\cr
D&:=A\hbox{ with decimal point shifted left $B$ places}\,;\cr
E&:=10*E\,.\cr}$$
This pattern works on the second line if the first line is initialized
$C=0$, $D=X$, $E=1$. The invariant of the algorithm is $X↑E=10↑C\times D$,
$E$~a~positive power of~10, $1≤D<10$. The logarithm of~$X$ is approximated
by~$C/E$, with an error less than~$1/E$.
The invariant $X↑E=10↑C\times D$ is preserved if I~raise $D$ to any power,
so long as I~multiply $E$ and~$C$ by the exponent. It is preserved if
I~divide $D$ by a power of~10, so long as I~increase $C$ by the exponent.
The above algorithm suggests a simpler one that gives the base--2 log of~$x$,
based not on raising numbers
to the tenth power, but on squaring them; the invariant of the last iteration is
$X↑E=2↑C\times D$, $E$~a~positive power of~2, $1≤D<2$.
{\obeylines\obeyspaces\let =\ \tt
READ(X); D:=X;
C:=0; E:=1;
WHILE D>=2 DO
BEGIN D:=0.5*D; C:=C+1; END; (* Now D<2 *)
WHILE D<1 DO
BEGIN D:=D+D; C:=C-1; END; (* Now 1<=D<2 *)
WHILE E<100000000 DO
BEGIN
D:=D*D; E:=E+E; C:=C+C;
IF D>=2 THEN
BEGIN D:=0.5*D; C:=C+1 END
END;
WRITELN(`BASE 2 LOG OF',X,`=',C/E)
}
%\vfill\eject
\medskip
{\rmn
\noindent
Note to users of calculators.
To raise a number $D$ to the tenth power, there is a better way than to do
nine multiplications, rekeying the multiplier every time. A~simple method uses
four multiplications:
{\obeylines\obeyspaces\let =\ \tt
D:=D*D; (* SQUARE *)
T:=D;
D:=D*D (* FOURTH POWER *)
D:=D*D*T
}
\noindent
On my calculator, the key sequence `$\times =$' squares the number in the
display, `M IN' saves the display in memory, and `MR' recalls memory to
the display, so the keystrokes `$\times =$ MIN $\times =\times =\times$
MR $=$' raise the display
to the tenth power.
}
\bigskip
The program fragment that follows is adapted from a better than average
textbook on programming in Pascal. It attempts to find a value of~$x$
for which $f(x)=0$. The idea is that the user gives the program values~$x↓1$
and~$x↓2$ for which $f(x↓1)$ and $f(x↓2)$ have opposite signs; the program
chooses~$x↓3$ between~$x↓1$ and~$x↓2$, where $f(x↓3)$ would be zero if
$f$~were linear, and replaces one of~$x↓1$, $x↓2$ with~$x↓3$ in such a way that
$x↓1$ and~$x↓2$ continue to have opposite signs.
\smallskip
{\obeylines\obeyspaces\let =\ \tt
BEGIN
GOODDATA:=FALSE; (* FLAG FOR ITERATION *)
WHILE NOT GOODDATA DO
BEGIN
INTERACTWRITELN('PLEASE ENTER TWO STARTING POINTS');
INTERACTREAD(X1,X2);
IF ((F(X1)<=0.0) AND (F(X2)>=0.0))
OR ((F(X1)>=0.0) AND (F(X1)<=0.0))
THEN GOODDATA:=TRUE
ELSE
INTERACTWRITELN('POINTS DO NOT BRACKET ROOT-TRY AGAIN')
END;
BEGIN
INTERACTWRITELN('PLEASE ENTER DESIRED ACCURACY');
INTERACTREAD(EPSILON);
ROOTFOUND:=FALSE; (* FLAG FOR ITERATION *)
COUNT:=0;
WHILE NOT ROOTFOUND AND COUNT<=100 DO
BEGIN
X3:=(X2*F(X1)-X1*F(X2))/(F(X1)-F(X2));
IF ((F(X1)<=0.0) AND (F(X3)>=0.0))
OR ((F(X1)>=0.0) AND (F(X3)<=0.0))
THEN X2:=X3
ELSE X1:=X3;
COUNT:=COUNT+1;
IF ABS(F(X3))<EPSILON
THEN ROOTFOUND:=TRUE
END;
IF ROOTFOUND
THEN INTERACTWRITELN('ROOT:',X3,'{\spa}TO ACCURACY',EPSILON)
ELSE WRITELN('UNABLE TO FIND ROOT')
END.
}
\smallskip\noindent
The program usually works if given two acceptable starting points. Nonetheless
it contains a time bomb that occasionally results in catastrophic failure,
defined to mean one of:
\smallskip
\display 25pt:$\bullet$:
grossly wrong results,
\display 25pt:$\bullet$:
running forever,
\display 25pt:$\bullet$:
execution of an invalid operation.
\smallskip\noindent
A program that fails in one of these ways is obviously unsatisfactory. If
it fails only occasionally, it may survive extensive testing, perhaps
failing when correct results are urgently needed.
Use the method of symbolic execution to find a function~$f$, and acceptable
values of~$x↓1$ and~$x↓2$, for which the program will fail.
\smallskip
[Symbolic execution gives {\tt X1} the value~{\tt A}, {\tt X2}~the value~{\tt B}.
One way to take the true branch of the first {\tt IF} statement is to have
$F(A)≤0$ and $F(B)≥0$. Then {\tt GOODDATA} becomes {\tt TRUE}, a~value~$C$
is read into {\tt EPSILON}, and {\tt X3} gets the value
$${B\,F(A)-A\,F(B)\over F(A)-F(B)}$$
which is undefined if $F(A)-F(B)=0$. The combination of all the conditions
above is $F(A)≤0$, $F(B)≥0$, $F(A)=F(B)$, or simply $F(A)=F(B)=0$. For
example, if $F(X)=X↑2-1$, $A=-1$, $B=+1$, the program will fail through
division by zero.]
\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd.
First draft July 2, 1984
%\line{\copyright 1985 Robert W. Floyd\hfill}
%\line{First draft (not published) October 1, 1985;\hfil}
%revised: Date; subsequently revised.\hfill}
\bye